//题目:
// 给定一个二维矩阵 matrix，以下类型的多个请求：
// 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
// 实现 NumMatrix 类：
// NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
// int sumRegion(int row1, int col1, int row2, int col2) 
// 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
#include<iostream>
#include<queue>
#include<unordered_map>
#include<limits.h>
#include<algorithm>

using namespace std;
//代码
class NumMatrix {
public:
    //vector<vector<int>> nums;
    int** dp;

    NumMatrix(vector<vector<int>>& matrix) 
    {
        //数组初始化    
        //nums=matrix;
        int rowcount=matrix.size();
        int colcount=matrix[0].size();

        dp=(int**)malloc(sizeof(int*)*rowcount);
        for(int i=0;i<rowcount;i++)
            dp[i]=(int*)malloc(sizeof(int)*colcount+1),dp[i][0]=0;
        for(int i=0;i<rowcount;i++)
        {
            for(int j=1;j<=colcount;j++)
            {
                dp[i][j]=dp[i][j-1]+matrix[i][j-1];
                //cout<<dp[i][j]<<" ";
            }
            //cout<<endl;
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) 
    {
        //初始化一个前缀和矩阵
        // vector<vector<int>> dp;
        // dp.reserve(rowcount);
        // for(int i=0;i<rowcount;i++)
        //     dp[i].reserve(colcount+1),dp[i][0]=0;
        int ret=0;
        for(int i=row1;i<=row2;i++)
        {
            ret+=dp[i][col2+1]-dp[i][col1];
        }

        // for(int i=0;i<rowcount;i++)
        //     free(dp[i]);
        // free(dp);
        return ret;
     }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */